package BloomFilter;

import java.util.BitSet;


class SimpleHash {
    public int cap; //当前容量
    public int seed; //随机数
    public SimpleHash(int cap,int seed){
        this.cap=cap;
        this.seed=seed;
    }
    //哈希函数
    public int hash(String key){
        int h;
        return  (key == null) ? 0 :(seed*cap-1) & (h = key.hashCode()) ^ (h >>> 16);
    }

}
public class MyBloomFilter {
    public static final int FINAL_SIZE=1<<20;
    //位图
    BitSet set;
    //记录了多少个数据
    int UsedSize;
    SimpleHash[] hash;
    //随机数数组
    public static final int[] seeds={9,22,3,4,55,6,77};
    public MyBloomFilter() {
        set=new BitSet(FINAL_SIZE);
        hash=new SimpleHash[seeds.length];
        for (int i = 0; i < seeds.length; i++) {
            hash[i]=new SimpleHash(FINAL_SIZE,seeds[i]);
        }
    }

    /**
     * 添加元素到布隆过滤器
     * @param val
     */
    public void add(String val) {
        for (int i = 0; i < hash.length; i++) {
           int x=hash[i].hash(val);
           set.set(x);
        }
    }

    /**
     * 检查元素是否存在
     * @param val
     * @return
     */
    public boolean contains(String val){
        for (int i = 0; i < hash.length; i++) {
            int x=hash[i].hash(val);
            if(!set.get(x)){
                return false;
            }
        }
        return true;
    }
}
class Main{
    public static void main(String[] args) {
        MyBloomFilter bloomFilter=new MyBloomFilter();
        bloomFilter.add("hello");
        System.out.println(bloomFilter.contains("hello"));
        System.out.println(bloomFilter.contains("he"));
    }
}
